package leetcode_300;

/**
 *@author 周杨
 *ShortestPalindrome_214 求一个字符串的最短回文串 如果其不是回文串 在前端补齐
 *describe:求字符串s的翻转s_rev
		将两个字符串进行拼接：{s}#{s_rev}
		找出新字符串中最长公共前缀后缀长度comLen
		s_rev.substring(0, s.length() - comLen)就是在原字符串头部插入的子串部分
举个例子：
 *2018年6月15日 下午4:29:33
 */
public class ShortestPalindrome_214_ {
	String s;
	public static void main(String[] args) {
		ShortestPalindrome_214_ test=new ShortestPalindrome_214_();
		/*System.out.println(test.shortestPalindrome("aacecaaa"));
		System.out.println(test.shortestPalindrome("abcd"));
		System.out.println(test.shortestPalindrome("aba"));*/
		System.out.println(test.getCommonLength("aacecaaa"));

	}
	public String shortestPalindrome1(String s) {
	       StringBuilder builder = new StringBuilder(s);
	        return builder.reverse().substring(0, s.length() - getCommonLength(s)) + s;
	    }
	   /**
	 * describe:kmp算法求最长前缀后缀公共串 
	 * 2018年6月15日 下午4:24:21
	 */
	private int getCommonLength(String str) {
	        StringBuilder builder = new StringBuilder(str);
	        String rev = new StringBuilder(str).reverse().toString();
	        builder.append("#").append(rev);
	        int[] p = new int[builder.length()];
	        for (int i = 1; i < p.length; i++) {
	            int j = p[i - 1];
	            while (j > 0 && builder.charAt(i) != builder.charAt(j)) j = p[j - 1];
	            p[i] = j == 0 ? (builder.charAt(i) == builder.charAt(0) ? 1 : 0) : j + 1;
	        }
	        return p[p.length - 1];
	    }
	
	/**
	 * describe:暴力解超时
	 * 2018年6月15日 下午4:23:55
	 */
	public String shortestPalindrome(String s) {
		this.s=s;
        if(s.length()<=1)
        	return s;
        int i=s.length();
        while(i<=s.length()) {
        	if(isPalindrome(i)) {
        		break;
        	}
        	--i;
        }
        StringBuilder sb=new StringBuilder(s.substring(i));
        sb.reverse();
        return sb.append(s).toString();
    }
	
	
	
	public boolean isPalindrome(int end) {
		int i=0,j=end-1;
		while(i<j) {
			if(s.charAt(i)!=s.charAt(j))
				return false;
			++i;
			--j;
		}
		return true;
	}
}
